/*
 * @lc app=leetcode.cn id=680 lang=java
 *
 * [680] 验证回文字符串 Ⅱ
 *
 * https://leetcode-cn.com/problems/valid-palindrome-ii/description/
 *
 * algorithms
 * Easy (34.12%)
 * Likes:    104
 * Dislikes: 0
 * Total Accepted:    10.5K
 * Total Submissions: 30.7K
 * Testcase Example:  '"aba"'
 *
 * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
 *
 * 示例 1:
 *
 *
 * 输入: "aba"
 * 输出: True
 *
 *
 * 示例 2:
 *
 *
 * 输入: "abca"
 * 输出: True
 * 解释: 你可以删除c字符。
 *
 *
 * 注意:
 *
 *
 * 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
 *
 *
 */

// @lc code=start
class Solution {
    public boolean validPalindrome(String s) {
        if(fun(s))
            return true;
        boolean flag = false;
        for(int i = 0; i < s.length(); i++) {
            flag |= fun(s.substring(0,i) + s.substring(i+1, s.length()));
            if(flag)
                return true;
        }
        return flag;

    }

    boolean fun(String s) {
        int left = 0, right = s.length() - 1;
        while(left < right) {
            if(s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
// @lc code=end

